The following prior art references are considered by applicant to be most pertinent to the present invention;
[A] D. T. Tang and L. R. Bahl, "Block Codes for a Class of Constrained Noiseless Channels," Information Control, No. 17, 1970. PA0 [B] G. F. M. Beenker and K. A. S. Immink, "A Generalized Method for Encoding and Decoding Run-Length-Limited Binary Sequences," IEEE Transactions on Information Theory, vol. IT-29, No. 5, 1983. PA0 [C] R. F. Lyon, "Two Level Block Encoding for Digital Transmission", IEEE Transactions on Communications, Com-21, 1438, 1973. PA0 [D] K. A. S. Immink, "Spectrum Shaping with Binary DC.sup.2 -constrained Codes," Phillip Journal of Research, Vol. 40, No. 1, 1985. PA0 [E] R. L. Adler, D. Coppersmith and M. Hassner, "Algorithms for Sliding Block Codes", IEEE Transactions on Information Theory, Vol. IT-29, No. 11, 1983.
In a block code with rate m/n, m-bit input strings are encoded into n output channel bits at a time with a fixed mapping.
Reference [A] first considered the application of lexicographical methods to encode and decode block codes with a (d, k) constrained sequence; i.e., codes expressed in non-return-to-zero increment (NRZI) notation, wherein run lengths have at least d and a maximum of k .0.'s between 1's.
The teachings of Reference [A] were extended by Reference [B] to improve the efficiency of block code concatenation; by Reference [C] to include direct current (dc)-free constrained block codes and disclose a practical embodiment thereof; and by Reference [D] to higher order dc-null block codes. All of these references employed block codes and used a universal ordering system wherein each codeword is in a fixed position in an ordered list.
Reference [D] refers to the possibility of state-dependent codes for improved code rates and calculates bounds for these code rates. There is no teaching of employing a state-dependent code in a lexicographical coding technique.
Reference [E] describes how sliding block codes are derived. From these codes an appropriate subset of (d,k) modulation sequences is determined for a preselected rate m/n code.
Encoding an arbitrary m-bit- binary sequence to an n-bit (d,k) sequence could be accomplished through the use of a lookup table with 2.sup.m n-bit entries, with the encoder mapping arbitrarily chosen. Decoding could be accomplished using a table with 2.sup.n m-bit entries which inverts the encoder mapping and recognizes any unused n-bit sequences, which are presumably flagged as invalid using an additional output bit. However, in many systems, storage of large tables is prohibitively costly, and it is therefore desirable to replace large tables with smaller size tables and some additional logic functions. This can be accomplished by use of lexicographical coding methods.
Lexicographical (or enumerative) coding refers to ordering coded sequences, much in the same way as a dictionary orders words so that they may be found easily. In magnetic recording, coded sequences come from a binary alphabet, and generally have the above described (d,k) constraints.
It is known that the use of state-dependent codes can improve the code rate over relatively short block codes. In attempting to apply lexicographical coding methods to state-dependent codes, it is necessary to contend with the problem that various code states may allow different sets of codewords. A universal ordering may include sequences which are not valid outputs from certain states. One solution is to employ separate encoders and decoders for each state, each using its own ordering, at the expense of multiplying the table size by the number of states.
There is a need for an efficient method for reducing storage by merging lookup tables for lexicographical coding of state-dependent (rather than block) codes, reducing hardware and speeding up decoding.